skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Creators/Authors contains: "Šileikis, Matas"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; (, Random Structures & Algorithms)
    Abstract We consider rooted subgraphs in random graphs, that is, extension counts such as (i) the number of triangles containing a given vertex or (ii) the number of paths of length three connecting two given vertices. In 1989, Spencer gave sufficient conditions for the event that, with high probability, these extension counts are asymptotically equal for all choices of the root vertices. For the important strictly balanced case, Spencer also raised the fundamental question as to whether these conditions are necessary. We answer this question by a careful second moment argument, and discuss some intriguing problems that remain open. 
    more » « less
  2. ; (, The Electronic Journal of Combinatorics)
    null (Ed.)
    For $$r \ge 2$$, let $$X$$ be the number of $$r$$-armed stars $$K_{1,r}$$ in the binomial random graph $$G_{n,p}$$.  We study the upper tail $${\mathbb P}(X \ge (1+\epsilon){\mathbb E} X)$$, and establish exponential bounds which are best possible up to constant factors in the exponent (for the special case of stars $$K_{1,r}$$ this solves a problem of Janson and Ruciński, and confirms a conjecture by DeMarco and Kahn).  In contrast to the widely accepted standard for the upper tail problem, we do not restrict our attention to constant $$\epsilon$$, but also allow for $$\epsilon \ge n^{-\alpha}$$ deviations. 
    more » « less
    Full Text Available 
  3. ; (, Random Structures & Algorithms)
    Given a fixed graph H, what is the (exponentially small) probability that the number XHof copies of Hin the binomial random graph Gn,pis at least twice its mean? Studied intensively since the mid 1990s, this so‐called infamous upper tail problem remains a challenging testbed for concentration inequalities. In 2011 DeMarco and Kahn formulated an intriguing conjecture about the exponential rate of decay of for fixed ε > 0. We show that this upper tail conjecture is false, by exhibiting an infinite family of graphs violating the conjectured bound. 
    more » « less